Encryption is essential in information communications via a computer network, in particular, in the VPN (Virtual Private Network) communications in which a public network mimics a dedicated line. And as the communication speed becomes higher, the required speed of the encryption becomes higher.
Common key cryptography, which is an encryption technique predominantly used in the computer network now, includes DES (Data Encryption Standard), AES (Advanced Encryption Standard) and Camellia. All of logic circuits (encryption circuits) for implementing these encryption techniques include a nonlinear converter unit, referred to as an S-Box, whose processing speed substantially affects the processing speed of the logic circuits themselves.
Now, an S-Box calculation in the common key cryptography and a method for constructing a circuit therefor will be described. Herein, the description is focused on the S-Box for the AES, for example.
The S-Box for the AES (i) applies on an 8-bit input multiplicative inversion in a GF (28) constituted by an irreducible polynomial x8+x4+x3+x+1 and then (ii) applies on the result an Affine transformation expressed by the following formula 1 to output an 8-bit value.
                              (                                                                      y                  ⁢                                                                          ⁢                  0                                                                                                      y                  ⁢                                                                          ⁢                  1                                                                                                      y                  ⁢                                                                          ⁢                  2                                                                                                      y                  ⁢                                                                          ⁢                  3                                                                                                      y                  ⁢                                                                          ⁢                  4                                                                                                      y                  ⁢                                                                          ⁢                  5                                                                                                      y                  ⁢                                                                          ⁢                  6                                                                                                      y                  ⁢                                                                          ⁢                  7                                                              )                +                              (                                                            1                                                  0                                                  0                                                  0                                                  1                                                  1                                                  1                                                  1                                                                              1                                                  1                                                  0                                                  0                                                  0                                                  1                                                  1                                                  1                                                                              1                                                  1                                                  1                                                  0                                                  0                                                  0                                                  1                                                  1                                                                              1                                                  1                                                  1                                                  1                                                  0                                                  0                                                  0                                                  1                                                                              1                                                  1                                                  1                                                  1                                                  1                                                  0                                                  0                                                  0                                                                              0                                                  1                                                  1                                                  1                                                  1                                                  1                                                  0                                                  0                                                                              0                                                  0                                                  1                                                  1                                                  1                                                  1                                                  1                                                  0                                                                              0                                                  0                                                  0                                                  1                                                  1                                                  1                                                  1                                                  1                                                      )                    ⁢                      (                                                                                x                    ⁢                                                                                  ⁢                    0                                                                                                                    x                    ⁢                                                                                  ⁢                    1                                                                                                                    x                    ⁢                                                                                  ⁢                    2                                                                                                                    x                    ⁢                                                                                  ⁢                    3                                                                                                                    x                    ⁢                                                                                  ⁢                    4                                                                                                                    x                    ⁢                                                                                  ⁢                    5                                                                                                                    x                    ⁢                                                                                  ⁢                    6                                                                                                                    x                    ⁢                                                                                  ⁢                    7                                                                        )                          +                  (                                                    1                                                                    1                                                                    0                                                                    0                                                                    0                                                                    1                                                                    1                                                                    0                                              )                                    [                  Formula          ⁢                                          ⁢          1                ]            “S-Box−1” indicates an inversion of this calculation.
To implement an S-Box circuit, there are two methods: (1) a GF inversion circuit and an Affine transformation circuit are constructed separately according to the definition described above and then connected in series to each other; and (2) the circuit is directly derived from relations between inputs and outputs (a truth table).
In the case of method (1), there may be adopted a calculation using the Fermat's little theorem P−1=P254 (for the GF(28)), a calculation using the extended Euclid's algorithm, or a conclusion to an inversion on a composite field. However, all of these are not suitable for high-speed implementation and have a circuit delay several times longer than that in method (2). For details of these techniques, see S. Morioka and Y. Katayama. “O(log2m) Iterative Algorithm for Multiplicative Inversion in GF (2m),” IEEE Intl. Symp. On Info. Theory (ISIT2000), pp. 449, 2000, and A. Satoh, S. Morioka, K. Takano and S. Munetoh, “A Compact Rijndael Hardware Architecture with S-Box Optimization,” ASIACRYPT2001, 2001.
On the other hand, in the case of method (2), there are known methods of constructing a logical formula in the form of product-sum, sum-product, or various Reed-Muller expressions, or method of various function expansions.
Next, a general logic synthesis algorithm for the combinational circuit will be described. As a logic construction method using a function expansion, a method using RO-BDD (Reduced Ordered Binary Decision Diagrams) is known. The RO-BDD is one of expression forms of logical formulas, and involves representing a process of Shannon expansion of a logical function in a certain sequence of variables as a binary decision diagram without closed circuit and removing any redundant node. Each node in the RO-BDD can be replaced with a 2:1 selector (MUX: multiplexer) to implement a circuit of the RO-BDD. Such a logic construction using the RO-BDD is described in detail in the following reference, R. E. Bryant; Graph-Based Algorithms for Boolean Function Manipulation, IEEE transactions on computers, Vol. C-35, No. 8, 1986.
The graph configuration of the RO-BDD corresponds to the resulting circuit configuration (relation among the connected selectors) substantially in one-to-one relationship. Therefore, determination of the configuration of the RO-BDD defines the circuit configuration. For a given logical function, there is more than one RO-BDD. There is design flexibility in sharing of nodes or sequence of variables.
FIG. 5 shows an arrangement of an S-Box for the AES based on the RO-BDD created according to a conventional logic synthesis algorithm. In FIG. 5, connections between selectors constituting the combinational circuit and between stages of the selectors are omitted appropriately.
As shown in FIG. 5, the S-Box combinational circuit based on the RO-BDD created according to the conventional logic synthesis algorithm has the following significant characteristics, which are not found in common logical functions.                Characteristic 1: on the output side of the circuit, few selectors are shared among outputs or selector groups for the same output. Sharing of selectors occurs in the first and second stages on the side of the input of the circuit. That is, from the output to the input, the number of selectors increases exponentially, 1*8, 2*8, 4*8, 8*8, . . . , and for substantially all the selectors, the fan-out of the output thereof is one. Then, the last two stages on the side of the input, the fan-out of the selector output is rapidly increased (about 30). To the contrary, many common logical functions, in which many selectors are shared in stages near the output, don't have such a tree structure as shown in FIG. 5. In addition, many nodes can be typically shared among outputs.        Characteristic 2: overall configuration of the coupled selectors is substantially independent of the sequence of input bits (which input bit drives which selector) and meets the above characteristic (1) for any sequence of bits. To the contrary, in many common logical functions, varying the sequence of input bits substantially changes the overall configuration of the circuit.        
As described above, in the past, the RO-BDD has been used to define the circuit configuration and design the combinational circuit. The fastest S-Box is a circuit obtained by automatic logic synthesis from a truth table of the S-Box. However, the S-Box involves an input/output definition that resembles the random number table, and thus, it is incompatible with general logical synthesis methods. Therefore, in the application for encryption described above, a sufficient speed could not be attained.
In other words, since the RO-BDD created according to the conventional logic synthesis algorithm has the above-described characteristics 1, 2, if the combinational circuit, such as the S-Box, is designed in such a manner that the RO-BDD is used to define the circuit configuration, the following two problems arise in designing a high-speed circuit.                (1) Fan-out of select signals and output data signals of selectors on the input side of the circuit is increased (in FIG. 5, for example, the second stage from the input includes 149 selectors, driving the select signals therefor is quite heavy. The selector output of each selector in the first stage from the input is needed to drive nearly 30 input signals for the selectors in the second stage, which is also quite heavy).        (2) The circuit comprises selectors connected to each other in series to form multiple stages, and thus, the time for signals to pass therethrough is long.        